package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 写之前就感觉这个dp推导有些问题, 虽然是倒退, 但是中间血量出现负数怎么整
 * <p>
 * 思考, 为什么要从右下角倒着来, 远哥他俩一开始从左上角想就卡死了
 *
 * @author tzp
 * @since 2020/10/26
 */
public class LC174 implements DynamicProblem {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];//从ij格子到右下角所需要的最低血量
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    dp[i][j] = dungeon[i][j] >= 0 ? 1 : -dungeon[i][j] + 1;
                } else {
                    int min = Integer.MAX_VALUE;
                    if (j + 1 < n) {//下
                        min = Math.min(min, -dungeon[i][j] + dp[i][j + 1]);
                    }
                    if (i + 1 < m) {//右
                        min = Math.min(min, -dungeon[i][j] + dp[i + 1][j]);
                    }
                    if (min <= 0) {
                        min = 1;
                    }
                    dp[i][j] = min;
                }
            }
        }
        return dp[0][0] <= 0 ? 1 : dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(new LC174().calculateMinimumHP(new int[][]{
                {1, -2, 3},
                {2, -2, -2}}));//2
        System.out.println(new LC174().calculateMinimumHP(new int[][]{
                {-3, 5}}));//4
        System.out.println(new LC174().calculateMinimumHP(new int[][]{
                {-2, -3, 3},
                {-5, -10, 1},
                {10, 30, -5}}));//7
    }
}
